1. Field of the Invention
The present invention relates to encoding and decoding of data in communication systems, and, more particularly, to encoders and decoders that implement both a product-code data encoding scheme and a data interleaving scheme.
2. Description of the Related Art
Many digital transmission systems commonly employ techniques for detection of digital data represented by a sequence of symbols. The symbol bits are transferred as a signal through a transmission (i.e., communication) channel in which noise is typically added to the transmitted signal. For example, magnetic recording systems first encode data into symbol bits that are recorded on a magnetic medium. Writing data to, storing data in, and reading data from the magnetic medium may be considered to take place via a transmission channel that has an associated frequency response. Similarly, each of wired, optical, wireless, and cellular communication systems also transfers encoded data through a channel, which encoded data is then detected and decoded by a receiver. The signal may be read from the channel as a sampled signal (i.e., a sequence of sample values) representing the transmitted encoded data. For processing convenience, the encoding and decoding process is applied to blocks of data, each block representing a portion of the original data sequence.
In order to accurately transmit and recover an original data sequence, some communication systems rely on both a data encoding scheme and a data interleaving scheme. In general, a data encoding scheme combines error detection/correction data with the original data sequence to generate an encoded data stream, where the error detection/correction data is derived from the original data sequence and enables a receiver of the encoded data stream to detect and possibly correct one or more data errors (e.g., bit errors) that occur during the transmission and/or reception of the encoded data stream.
A data interleaving scheme rearranges the order of the data in a transmitted stream such that, after de-interleaving is performed at the receiver, sequences of consecutive data errors (e.g., resulting from bursty noise in the transmission channel or sample timing errors at the receiver) are distributed (i.e., spread out such that they are no longer consecutive) in the de-interleaved stream. Distributing the errors increases the chances that the receiver will be able to successfully detect and possibly correct all of the data errors using the error detection/correction data encoded into the transmitted stream.
One known type of data encoding scheme is based on product-code (PC) encoding. In two-dimensional PC encoding, N original data bits are arranged in an (n row×m column) rectangular matrix, where N=nm. Each of the n rows in the matrix represents an m-element data vector in one dimension of the 2D product code, and each of the m columns in the matrix represents an n-element data vector in the other dimension of the 2D product code. A check-code operation (e.g., based on Galois field 2 (GF(2)) addition, multiplication, or other linear operation) is then independently applied to each row data vector to generate a codeword row containing the row's original m data bits and one or more row-wise parity bits for that row. The same or another check-code operation is also independently applied to each original column data vector to generate a codeword column containing the column's original n data bits and one or more column-wise parity bits for that column.
In general, a receiver of the PC-encoded data can use the codeword rows and columns to perform some level of error detection and possibly even error correction for the received data. When single-bit parity check codes are employed on a per dimension basis, product codes typically exhibit optimum performance with respect to coding gain when correcting for single one-bit errors. In that case, only single, one-bit errors may be detected and corrected because of parity-check cancellation arising from an even number of errors occurring in a row or column and parity-check positional ambiguities associated with multiple one-bit errors.
The ability of a receiver to detect and possibly correct consecutive transmission/reception errors (i.e., burst errors) is increased when the data encoding scheme, such as a PC-encoding scheme, is implemented with a data interleaving scheme that distributes such errors in the de-interleaved stream. In general, an interleaving scheme may be represented by a mapping that maps each location of data in the un-interleaved (i.e., before interleaving) data stream to a corresponding location of data in the interleaved data stream. There are two basic types of interleaving schemes: structured interleaving and random interleaving.
In structured interleaving, the mapping can be represented by a closed-form mathematical expression whose input is one or more numbers that represent the un-interleaved location and whose output is one or more numbers that represent the corresponding interleaved location. As such, a structured interleaver for a transmitter can be designed to implement the closed-form mathematical expression to generate the interleaved location for each un-interleaved location. If the closed-form mathematical expression can be inverted, then a structured de-interleaver for a receiver can be designed to implement one or more inverted, closed-form mathematical expressions to generate the de-interleaved location for each interleaved location.
For purposes of this specification, a closed-form mathematical expression may be defined as an mathematical equation having one or more variables, where evaluation of the mathematical equation generates a numerical output value when the one or more variables are replaced by a corresponding set of one or more numerical input values. A closed-form mathematical expression may be said to be invertible, if there is a unique output value for each different set of input values and one or more closed-form mathematical expressions can be derived to map each of those different output values to its corresponding one or more input values.
In random interleaving, there is no closed-form mathematical expression for either the mapping from un-interleaved locations to interleaved locations or the mapping from interleaved locations to de-interleaved locations. In that case, random interleavers/de-interleavers are often implemented using look-up tables (LUTs) that explicitly relate each input location to its corresponding output location.
A conventional transmitter that implements both PC-encoding and interleaving is typically designed with a PC encoder that generates a block of PC-encoded data for each block of original data and a separate interleaver that maps each block of PC-encoded data into a stream of interleaved, PC-encoded data. Similarly, a corresponding receiver is typically designed with a de-interleaver that maps the stream of received, interleaved, PC-encoded data into blocks of de-interleaved, PC-encoded data and a separate PC decoder that generates a block of recovered data for each block of de-interleaved, PC-encoded data.